package com.shm.leetcode;

import sun.reflect.generics.tree.Tree;

/**
 * @author: shm
 * @dateTime: 2020/9/16 19:10
 * @description: 226. 翻转二叉树
 * 翻转一棵二叉树。
 *
 * 示例：
 *
 * 输入：
 *
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 * 输出：
 *
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 * 备注:
 * 这个问题是受到 Max Howell 的 原问题 启发的 ：
 *
 * 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
 */
public class InvertTree {
    public TreeNode invertTree(TreeNode root) {
        if (root!=null) {
            swapNode(root);
        }
        return root;
    }

    public void swapNode(TreeNode node){
        if (node.left==null && node.right==null){
            return;
        }
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        if (node.left!=null){
            swapNode(node.left);
        }
        if (node.right!=null){
            swapNode(node.right);
        }
    }

    public TreeNode invertTree_2(TreeNode root) {
        if(root==null){
            return root;
        }
        TreeNode ans = new TreeNode();
        preOrder(root,ans);
        return ans;
    }

    void preOrder(TreeNode root,TreeNode ans){
        if(root==null){
            return;
        }
        ans.val = root.val;
        if(root.left!=null){
            ans.right = new TreeNode();
            preOrder(root.left,ans.right);
        }
        if(root.right!=null){
            ans.left = new TreeNode();
            preOrder(root.right,ans.left);
        }
    }

    /**
     * 方法一：递归
     * 思路与算法
     *
     * 这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子结点先开始翻转。如果当前遍历到的节点 \textit{root}root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 \textit{root}root 为根节点的整棵子树的翻转。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(N)O(N)，其中 NN 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
     *
     * 空间复杂度：O(N)O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(\log N)O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)O(N)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/invert-binary-tree/solution/fan-zhuan-er-cha-shu-by-leetcode-solution/
     * @param root
     * @return
     */
    public TreeNode invertTreeNode(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode left = invertTreeNode(root.left);
        TreeNode right = invertTreeNode(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
